
res = 0
a = [[-1] * 6 for _ in range(6)]

# 当前行和 放置的数
def work(i, x):
    for j in range(1, n + 1):
        # 模拟 放置棋子 0 1
        a[i][n - j + 1] = (x >> (j - 1)) & 1

def check1(x):
    cnt = sum(a[x][1:n+1])
    return cnt != 0 and cnt != n

def check2(y):
    cnt = sum(a[i][y] for i in range(1, n + 1))
    return cnt != 0 and cnt != n

def check3():
    cnt = sum(a[i][i] for i in range(1, n + 1))
    return cnt != 0 and cnt != n

def check4():
    cnt = sum(a[i][n - i + 1] for i in range(1, n + 1))
    return cnt != 0 and cnt != n

def dfs(dep, num1, num2):
    global res
    if dep == n + 1:
        for i in range(1, n + 1):
            if not check1(i) or not check2(i):
                return
        if not check3() or not check4():
            return
        res += 1
        return
    # 位运算 模拟 每一行棋子放置的情况
    for i in range(1, (1 << n)):
        # 统计1的次数
        cnt1 = bin(i).count('1')
        cnt2 = n - cnt1
        # 棋子数 > 和棋时的棋子数，跳过
        if cnt1 + num1 > n * n // 2 + (n % 2) or cnt2 + num2 > n * n // 2:
            continue
        # 当前行 和 放置的数
        work(dep, i)
        dfs(dep + 1, num1 + cnt1, num2 + cnt2)

n = 5
dfs(1, 0, 0)
print(res)

print(3126376)